package leetcode

import "github.com/dingkegithub/datastrcture/stackqueue"

/*
Tags
array | two-pointers | stack

Companies
amazon | apple | bloomberg | google | twitter | zenefits

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。


输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2,  1


```
  /|\
   |
 4 +
   |
 3 +                                               +-----+
   |                                               |  \  |
 2 +                       +-----+.................|  \  +-----+.....+-----+
   |                       |  \  |.................|  \  \  \  |.....|  \  |
 1 +           +-----+.....|  \  +-----+.....+-----+  \  \  \  +-----+  \  +-----+
   |           |  \  |.....|  \  \  \  |.....|  \  \  \  \  \  \  \  \  \  \  \  |
 0 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-->
         0     1     2     3     4     5     6     7     8     9     10    11    12
```
           0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
src     = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2,  1]
leftMax = [0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3,  3]
rightMax= [3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2,  1]

              0, 1, 0, 1, 2, 1, 0, 0, 1, 0, 0] => 6

实例1中图中虚线所示为可接水的地方，2~3， 4~7, 5~6， 9~10 之间可以接水，可接水：

1 + 1 + 3 + 1 = 6, 总共为6个单位的水


输入：height = [4,2,0,3,2,5]
输出：9
 0,  1,  2,  3,  4,  5
 4   2   0,  3,  2,  5

```
  /|\
   |
 5 +                                   +-----+
   |                                   |  \  |
 4 +     +-----+.......................|  \  |
   |     |  \  |.......................|  \  |
 3 +     |  \  |...........+-----+.....|  \  |
   |     |  \  |...........|  \  |.....|  \  |
 2 +     |  \  +-----+.....|  \  +-----+  \  |
   |     |  \  \  \  |.....|  \  \  \  \  \  |
 1 +     |  \  \  \  |.....|  \  \  \  \  \  |
   |     |  \  \  \  |.....|  \  \  \  \  \  |
 0 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-->
         0     1     2     3     4     5     6     7     8     9     10
```

可以接水的地方 1~3, 2~3, 4~5, 面积为:

      (3-2) * 2 + (3-1) * 1 + (5-4) * 1 + (5-1) * 1 = 2 + 2 + 1 + 4 = 9

提示：

n == height.length
0 <= n <= 3 * 104
0 <= height[i] <= 105
*/

/*

桶 盛水原理
```
     左边                 右边       刻度
       ||                             4 +-
       ||                               |
       ||~~~~~~~~~~~~~~~~~||          3 |-
       ||~~~~~~~~~~~~~~~~~||            |
       ||~~~~~~~~~~~~~~~~~||          2 |-
       ||~~~~~~~~~~~~~~~~~||            |
	   ||=================||桶底      1 |-
	   ||\\\\\\\\\\\\\\\\\||            |
	   ++=================++          0 |-
```
看上面桶，桶左边高4， 右边框高3， 桶底比较厚，有1个公分，那么实际该桶能盛水有低一边和桶底决定，
所以所剩水为：min(桶左边高度，桶右边高度) - 桶底高度 = min（4, 3) - 1 = 3 - 1 =2



解法1：暴力求解，主要思路是求解当前节点上方能存多少水, 我们把每个位置的高度假设为桶底

     0 位置左边不能存水，数组最右边也不能存水，因此再(0, size-1) 之间求， 需要两层
循环，外层控制在(0, size-1), 内存循环分别向左右寻找最高节点，为啥找最高，最高才能
容得下当前节点，当前节点时桶底，两边或一边比桶底低，怎么能容得下水

1 位置，左边最高为0位置4， 右边最高为5位置5，两者取其小，4， 减去当前的高度2， 4-2=2， 也就是说1位置上方能存2个单位的水

2 位置，左边最高4，右边最高为5，取其小为4，当前高度为0，那就是当前上方最多存 4-0=4 个单位的水

3 位置，左边最高4，右边最高为5，取其小为4，当前高度为3，那就是当前上方最多存 4-3=1 个单位的水

4 位置，左边最高4，右边最高为5，取其小为4，当前高度为2，那就是当前上方最多存 4-2=2 个单位的水

5 位置，当了边界，结束，最后棉结为上面所有位置可接水的和，即：2 + 4 + 1 + 2 = 9 个单位二的水

```
  /|\
   |
 5 +                                   +-----+
   |                                   |  \  |
 4 +     +-----+.......................|  \  |
   |     |  \  |.......................|  \  |
 3 +     |  \  |...........+-----+.....|  \  |
   |     |  \  |...........|  \  |.....|  \  |
 2 +     |  \  +-----+.....|  \  +-----+  \  |
   |     |  \  \  \  |.....|  \  \  \  \  \  |
 1 +     |  \  \  \  |.....|  \  \  \  \  \  |
   |     |  \  \  \  |.....|  \  \  \  \  \  |
 0 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-->
         0     1     2     3     4     5     6     7     8     9     10
```

时间复杂度： O(n^2) 数组中的每个元素都需要向左向右扫描。

空间复杂度 O(1) 的额外空间。

*/
func JieYuShui(height []int) int {
	ans, size := 0, len(height)

	for i := 1; i < size-1; i++ {
		max_left, max_right := 0, 0

		// 当前位置开始向左搜索最高的位置
		for j := i; j >= 0; j-- {
			max_left = max(max_left, height[j])
		}

		// 当前位置开始向右搜索最高的位置
		for j := i; j < size; j++ {
			max_right = max(max_right, height[j])
		}

		// 左右最高取其小减去桶底就是当前位置所能接的水
		// 最后所有位置可接的水加起来就是总供给接的水
		ans += min(max_left, max_right) - height[i]
	}
	return ans
}

func max(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

func min(a, b int) int {
	if a < b {
		return a
	} else {
		return b
	}
}

/*

桶 盛水原理
```
     左边                 右边       刻度
       ||                             4 +-
       ||                               |
       ||~~~~~~~~~~~~~~~~~||          3 |-
       ||~~~~~~~~~~~~~~~~~||            |
       ||~~~~~~~~~~~~~~~~~||          2 |-
       ||~~~~~~~~~~~~~~~~~||            |
	   ||=================||桶底      1 |-
	   ||\\\\\\\\\\\\\\\\\||            |
	   ++=================++          0 |-
```
看上面桶，桶左边高4， 右边框高3， 桶底比较厚，有1个公分，那么实际该桶能盛水有低一边和桶底决定，
所以所剩水为：min(桶左边高度，桶右边高度) - 桶底高度 = min（4, 3) - 1 = 3 - 1 =2


解法2： 开辟额外的空间，然后存储每个节点的左右最高节点，当前节点仍然为桶底，开辟两个空间，一个存储

桶的左边最高高度，一个存放右边最高高度，最后左右两个高度取其小，减去桶底就是当前节点可容水
```
  /|\
   |
 5 +                                   +-----+
   |                                   |  \  |
 4 +     +-----+.......................|  \  |
   |     |  \  |.......................|  \  |
 3 +     |  \  |...........+-----+.....|  \  |
   |     |  \  |...........|  \  |.....|  \  |
 2 +     |  \  +-----+.....|  \  +-----+  \  |
   |     |  \  \  \  |.....|  \  \  \  \  \  |
 1 +     |  \  \  \  |.....|  \  \  \  \  \  |
   |     |  \  \  \  |.....|  \  \  \  \  \  |
 0 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-->
         0     1     2     3     4     5     6     7     8     9     10
```

其实本质上和上面解法1 一样，只是解法1两层循环，时间负载度为 O(n²), 我们这里进行三个单独的for
循环，第一次求出每个节点左边最高高度，第二次求出每个节点右边最高高度，第三次for循环两个桶变
高度和当前节点桶底比较算出可容水, 下面我们画出桶看看


第一次for循环：
                 0  1  2  3  4  5
    src      -> [4, 2, 0, 4, 2, 5]
	leftMax  -> [4, 4, 4, 4, 4, 5]

第二次for循环：
                 0  1  2  3  4  5
    src      -> [4, 2, 0, 4, 2, 5]
    rightMax -> [5, 5, 5, 5, 5, 5]

第三次for循环：

    min(leftMax[i], rightMax[i]) - height[i]
    area     -> [0, 2, 4, 1, 2] 求和为 9

时间复杂度：O(n) 三次for循环，理解为O(3n), 舍去常量得到 O(n)
空间复杂度：O(2n), 额外开辟两个数组存放左右边沿高度

结论：有时候开始两层for 循环代码简洁，第二种很傻瓜按照一步一步按部就班写代码，似乎很傻，但是
执行效率可能提升了，编程除了解决问题，对硬件资源来说还是空间和时间的取舍
*/
func JieYuShuiL2(height []int) int {
	size := len(height)
	if size <= 0 {
		return 0
	}

	ans := 0

	// leftMax 存储每个节点桶左边沿的最高高度
	leftMax := make([]int, size)

	// rightMax 存储每个节点桶右边沿的最高高度
	rightMax := make([]int, size)

	// 第一次for循环，存储所有节点左边的高度
	leftMax[0] = height[0]

	for i := 1; i < size; i++ {
		leftMax[i] = max(height[i], leftMax[i-1])
	}

	// 第二次for循环，存储所有节点右边的高度
	rightMax[size-1] = height[size-1]

	for i := size - 2; i >= 0; i-- {
		rightMax[i] = max(height[i], rightMax[i+1])
	}

	// 第三次for循环，计算每个节点储水量，同时求和得出盛水量
	for i := 1; i < size-1; i++ {
		ans += min(leftMax[i], rightMax[i]) - height[i]
	}

	return ans
}

/*
```
  /|\
   |
 5 +                                   +-----+
   |                                   |  \  |
 4 +     +-----+=======================|  \  |
   |     |  \  |..........a4...........|  \  |
 3 +     |  \  |===========+-----+=====|  \  |
   |     |  \  |....a2.....|  \  |..a3.|  \  |
 2 +     |  \  +-----+=====|  \  +-----+  \  |
   |     |  \  \  \  |.....|  \  \  \  \  \  |
 1 +     |  \  \  \  |.a1..|  \  \  \  \  \  |
   |     |  \  \  \  |.....|  \  \  \  \  \  |
 0 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-->
         0     1     2     3     4     5     6     7     8     9     10
```

前面是用桶形模型求每个点的容量，现在换个思想横向求解，引入栈的概念，入栈的条件
是栈顶比栈低元素小，一旦即将准备要入栈的元素大于栈顶，那么当前栈顶的容量有次栈顶
和当前即将入栈的这个元素决定，形成一个长方形，计算面积

                 0  1  2  3  4  5
    src      -> [4, 2, 0, 3, 2, 5]

将上面的元素入栈，当 3-》3 准备入栈是发现大于栈顶元素，所以栈顶2->0由当前 3->3

和次栈顶 1->2 元素决定，3->3 到 1->2 的距离是宽度，1->2 和 3->3 较低的一边就是

高度，即 1->2， 最后减去暂定高度 2->0 ，就是 2-0=2 得到高度，面积就是 w * h = (3-1) * min(2, 3)-0 = 4

这样就得到 a1 的面积 4
```
 3->3 --+
       \|/
     |      |
     +------+
     |      |
     +------+
     |      |
     +------+
     |      |
     +------+
     | 2->0 |
     +------+
     | 1->2 |
     +------+
     | 0->4 |
     +------+
```

```
  /|\
   |
 5 +                                   +-----+
   |                                   |  \  |
 4 +     +-----+=======================|  \  |
   |     |  \  |..........a4...........|  \  |
 3 +     |  \  |===========+-----+=====|  \  |
   |     |  \  |....a2.....|  \  |..a3.|  \  |
 2 +     |  \  +-----+=====|  \  +-----+  \  |
   |     |  \  \  \  |.....|  \  \  \  \  \  |
 1 +     |  \  \  \  |.a1..|  \  \  \  \  \  |
   |     |  \  \  \  |.....|  \  \  \  \  \  |
 0 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-->
         0     1     2     3     4     5     6     7     8     9     10
```

前面是用桶形模型求每个点的容量，现在换个思想横向求解，引入栈的概念，入栈的条件
是栈顶比栈低元素小，一旦即将准备要入栈的元素大于栈顶，那么当前栈顶的容量有次栈顶
和当前即将入栈的这个元素决定，形成一个长方形，计算面积

                 0  1  2  3  4  5
    src      -> [4, 2, 0, 3, 2, 5]

将上面的元素入栈，当 3-》3 准备入栈是发现大于栈顶元素，所以栈顶1->2 由当前 3->3

和次栈顶 0->4 元素决定，3->3 到 0->4 的距离是宽度，0->4 和 3->3 较低的一边就是

高度，即 3->3， 最后减去栈顶高度 1->2 ，就是 3-2=1 得到高度，面积就是 w * h = (3-0-1) * (min(3, 4)-2) = 2 * 1 = 2

这样就得到 a2 的面积 2
```
 3->3 --+
       \|/
     |      |
     +------+
     |      |
     +------+
     |      |
     +------+
     |      |
     +------+
     |      |
     +------+
     | 1->2 |
     +------+
     | 0->4 |
     +------+


```


```
  /|\
   |
 5 +                                   +-----+
   |                                   |  \  |
 4 +     +-----+=======================|  \  |
   |     |  \  |..........a4...........|  \  |
 3 +     |  \  |===========+-----+=====|  \  |
   |     |  \  |....a2.....|  \  |..a3.|  \  |
 2 +     |  \  +-----+=====|  \  +-----+  \  |
   |     |  \  \  \  |.....|  \  \  \  \  \  |
 1 +     |  \  \  \  |.a1..|  \  \  \  \  \  |
   |     |  \  \  \  |.....|  \  \  \  \  \  |
 0 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-->
         0     1     2     3     4     5     6     7     8     9     10
```


前面是用桶形模型求每个点的容量，现在换个思想横向求解，引入栈的概念，入栈的条件
是栈顶比栈低元素小，一旦即将准备要入栈的元素大于栈顶，那么当前栈顶的容量有次栈顶
和当前即将入栈的这个元素决定，形成一个长方形，计算面积

                 0  1  2  3  4  5
    src      -> [4, 2, 0, 3, 2, 5]

到入栈到 5-> 5 时大于栈顶

最后算出 a3=1, a4=3

总容量 = a1 + a2 + a3 + a4 = 2 + 2 + 1 + 4 = 9

```
 5->5 --+
       \|/
     |      |
     +------+
     |      |
     +------+
     |      |
     +------+
     |      |
     +------+
     | 4->2 |
     +------+
     | 3->3 |
     +------+
     | 0->4 |
     +------+
```

*/
func JieYuShuiL3(height []int) int {
	size := len(height)
	if size <= 0 {
		return 0
	}

	area, cur := 0, 0
	stack := stackqueue.NewStack()

	for cur = 0; cur < size; cur++ {

		for !stack.Empty() {
			// 查询取出栈顶的元素
			top, _ := stack.Peek()

			// 栈顶元素 > 当前元素，则结束for 循环
			if height[cur] <= height[top.(int)] {
				break
			}

			// 弹出栈顶元素
			stack.Pop()

			// 查询新栈顶元素
			newTop, _ := stack.Peek()

			// 当前元素和新栈顶的距离
			w := cur - newTop.(int) - 1

			// 求出高度
			h := min(height[cur], height[newTop.(int)]) - height[top.(int)]

			// 面积
			area += w * h
		}

		// 入栈
		stack.Push(cur)
	}
	return area
}
